<h2>Problem 244</h2>
<div style="color:#666;font-size:80%;">09 May 2009</div><br />
<div class="problem_content">
<p>You probably know the game <i>Fifteen Puzzle</i>. Here, instead of numbered tiles, we have seven red tiles and eight blue tiles.</p>
<p>A move is denoted by the uppercase initial of the direction (Left, Right, Up, Down) in which the tile is slid, e.g. starting from configuration (<b>S</b>), by the sequence <b>LULUR</b> we reach the configuration (<b>E</b>):</p>
<p><div style="text-align: center;">
<table cellspacing='0' cellpadding='2' border='0' align='center'>
<tr><td width = '25'>(<b>S</b>)</td><td width='100'><img src="project/images/p_244_start.gif" /></td><td width = '25'>,&nbsp;(<b>E</b>)</td><td width='100'><img src="project/images/p_244_example.gif" /></td>
</table>
</div>
</p>
<p>For each path, its checksum is calculated by (pseudocode):
<div style="margin-left: 100px;">
checksum = 0<br />
checksum = (checksum <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 243 + <var>m</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />) mod 100&thinsp;000&thinsp;007<br />
checksum = (checksum <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 243 + <var>m</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" />) mod 100&thinsp;000&thinsp;007<br />
&nbsp;&nbsp;&nbsp;&hellip;<br />
checksum = (checksum <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 243 + <var>m</var><img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" />) mod 100&thinsp;000&thinsp;007<br />
</div>
where <var>m</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var></sub><img src="" style="display:none;" alt=")" /> is the ASCII value of the <var>k</var><img src="" style="display:none;" alt="^(" /><sup><var>th</var></sup><img src="" style="display:none;" alt=")" /> letter in the move sequence and the ASCII values for the moves are:

<div style='text-align:center;'>
<table cellspacing='0' cellpadding='2' border='1' align='center'>
<tr><td width='30'><b>L</b></td><td width='30'>76</td></tr>
<tr><td><b>R</b></td><td>82</td></tr>
<tr><td><b>U</b></td><td>85</td></tr>
<tr><td><b>D</b></td><td>68</td></tr>
</table>
</div>
</p>
<p>For the sequence <b>LULUR</b> given above, the checksum would be 19761398.</p>
<p>Now, starting from configuration (<b>S</b>),
find all shortest ways to reach configuration (<b>T</b>).</p>
<p><div style="text-align: center;">
<table cellspacing='0' cellpadding='2' border='0' align='center'>
<tr><td width = '25'>(<b>S</b>)</td><td width='100'><img src="project/images/p_244_start.gif" /></td><td width = '25'>,&nbsp;(<b>T</b>)</td><td width='100'><img src="project/images/p_244_target.gif" /></td>
</table>
</div>
</p>
<p>What is the sum of all checksums for the paths having the minimal length?</p>
</div><br />
